package com.wtgroup.demo.leetcode.q005_最长回文子串;

public class S_CenterExpand {
    /*
    中心扩散

    S_Force： 长度递增时，每个长度下，都要遍历一遍，每个子串判断是否回文时，子的子每次都要重新判断。
    动态规划思路：子的子结果复用。稍好。
    但，由于动态规划的特性，需要很多无谓的遍历。
    本思路：去掉外层长度循环。某个字串只会判断一次。
    O(n2)

    效果: 快于 动态规划. 看来是因为减少了很多无畏的循环(内含判断).
    */
    public String longestPalindrome(String s) {

        int n = s.length();
        // String ans = "";
        int maxLen = 1;
        int begin = 0;

        for (int i = 0; i < n; i++) {
            // 奇数个, 偶数个
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i+1);
            int len = Math.max(len1, len2);
            if(len > maxLen) {
                // Tip: 计算开始位置, i往左移动i的左边长度即是.
                // len为奇数的, 等价 len/2, 即i的左边长度; len为偶数的, len-1, i 就刚好是正中间. (len-1)/2 和奇数的效果一样了.
                // int st = i - (len-1) / 2;
                // ans = s.substring(st, st+len);
                maxLen = len;
                begin = i - (len-1) / 2;
            }
        }

        return s.substring(begin, begin + maxLen);
    }

    private int expand(String s, int lt, int rt) {
        while(lt>=0 && rt<s.length() && s.charAt(lt) == s.charAt(rt)) {
            lt--; rt++;
        }
        return rt - lt - 1;
    }

    public static void main(String[] args) {
        String[] ss = {"babad", "cbbd", "a", "ac", "fgosujtgyeowsyhuermhldjhldrdlgjslgjfsaopyrtgujsdlhkjlsegjsl"};
        for (String s : ss) {
            System.out.println(new S_CenterExpand().longestPalindrome(s));
        }
    }

}
